package AdditiveNumber;

import java.math.BigDecimal;

public class Solution {
	    public boolean isAdditiveNumber(String num) {
	        for (int i=2;i<num.length();i++){
	          String sub=num.substring(0, i);
	          for (int j=1;j<sub.length();j++){
	        	  String oneString=sub.substring(0, j);
	        	  if (oneString.charAt(0)=='0' && oneString.length()>1) continue;
	        	  String twoString=sub.substring(j);
	        	  if (twoString.charAt(0)=='0' && twoString.length()>1) continue;
	        	  BigDecimal one=new BigDecimal(oneString);
	        	  BigDecimal two=new BigDecimal(twoString);
	        	  boolean bo=check(num.substring(i),one,two);
	        	  if (bo) return true;
	          }
	          
	    }
	        return false;
        }

		private boolean check(String substring, BigDecimal one, BigDecimal two) {
			BigDecimal three=one.add(two);
			String threeString=three.toString();
			if (threeString.startsWith("0") && threeString.length()>1) return false;
			if (substring.startsWith(threeString)){
				if (substring.equals(threeString)) return true;
				else return check(substring.substring(threeString.length()),two,three);
			}
			else return false;
		}
		public static void main(String args[]) {
			String t="101";
			Solution so=new Solution();
			System.out.println(so.isAdditiveNumber(t));
		}
}